#include<stdio.h>
#include<Matrix/LB_Matrix.h>
#include<Matrix/LB_MatrixOperator.h>
#include<Algorithm/subdivision_of_polygon.h>
#include<time.h>

//buxiangjiao 
// 0.62164989114 1.44138810039 -1.59977641702 
// 2.30553117394 2.26631274819 -0.90405902267 
// 0.53100573272 2.18504884839 -2.26215532422 
// 2.21488701552 3.00997349620 -1.56643792987 
// 2 0 1 
// 2 2 3 
void test1()
{
    double p[3]={0};
    double p1[3]={0.62164989114,1.44138810039, -1.59977641702};
    double p2[3]={2.30553117394, 2.26631274819, -0.90405902267};
    double q1[3]={0.53100573272, 2.18504884839, -2.26215532422};
    double q2[3]={2.21488701552, 3.00997349620, -1.56643792987};
    int re=is_line_segment_intersecting_with_line_segment(q1,q2,p1,p2,p);

    printf("re:%d %f %f %f\n",re,p[0],p[1],p[2]);
}

// 0.17161042988 0.27831220627 0.01559102908 
// 1.15984053910 0.18718500435 -0.10710972175 
// 0.73456984013 0.67241380364 0.18215382472 
// 0.59688112885 -0.20691659302 -0.27367251739 
// 2 0 1 
// 2 2 3 

void test2()
{
    double p[3]={0};
    double p1[3]={0.17161042988,0.27831220627,0.01559102908};
    double p2[3]={1.15984053910,0.18718500435,-0.10710972175};
    double q1[3]={0.73456984013,0.67241380364,0.18215382472 };
    double q2[3]={0.59688112885,-0.20691659302,-0.27367251739 };
    int re=is_line_segment_intersecting_with_line_segment(q1,q2,p1,p2,p);

    printf("re:%d %f %f %f\n",re,p[0],p[1],p[2]);
}

// 1.17910423875 1.38418064266 -0.80603528023 
// 1.53689408302 3.09332416207 0.16904604435 
// 1.17913354176 1.38419591608 -0.80607280388 
// 2.35122480989 1.99511746317 -2.30698156357 
// 2 0 1 
// 2 2 3 

void test3()
{
    double p[3]={0};
    double p1[3]={1.17910423875, 1.38418064266, -0.80603528023};
    double p2[3]={1.53689408302, 3.09332416207, 0.16904604435};
    double q1[3]={1.17913354176, 1.38419591608, -0.80607280388  };
    double q2[3]={2.35122480989, 1.99511746317, -2.30698156357};
    int re=is_line_segment_intersecting_with_line_segment(q1,q2,p1,p2,p);

    printf("re:%d %f %f %f\n",re,p[0],p[1],p[2]);
}
// 1.65793032944 0.57116483152 -1.12408406194 
// 1.94854845107 2.04146169126 0.20020120684 
// 1.94858579460 2.04147956212 0.20017317047 
// 3.44232730690 2.75631377537 -0.92128154526 
// 2 0 1 
// 2 2 3 

void test4()
{
    double p[3]={0};
    double p1[3]={1.65793032944, 0.57116483152, -1.12408406194};
    double p2[3]={1.94854845107, 2.04146169126, 0.20020120684};
    double q1[3]={1.94858579460, 2.04147956212, 0.20017317047  };
    double q2[3]={3.44232730690, 2.75631377537, -0.92128154526 };
    int re=is_line_segment_intersecting_with_line_segment(q1,q2,p1,p2,p);

    printf("re:%d %f %f %f\n",re,p[0],p[1],p[2]);
}
// 0.62454126775 0.88657394052 -0.30876103044 
// 0.78615637124 2.07970562577 1.28817996383 
// 0.62449837024 0.88655563494 -0.30874301168 
// 2.34044180810 1.61879703403 -1.02951130271 
// 2 0 1 
// 2 2 3 

void test5()
{
    double p[3]={0};
    double p1[3]={0.62454126775, 0.88657394052, -0.30876103044};
    double p2[3]={0.78615637124, 2.07970562577, 1.28817996383 };
    double q1[3]={0.62449837024, 0.88655563494, -0.30874301168  };
    double q2[3]={2.34044180810, 1.61879703403, -1.02951130271 };
    int re=is_line_segment_intersecting_with_line_segment(q1,q2,p1,p2,p);

    printf("re:%d %f %f %f\n",re,p[0],p[1],p[2]);
}
// 2.19479724765 0.08228617162 -0.93576115370 
// 2.29866822064 2.07003002614 -0.74083438516 
// 2.24677723010 1.07615801043 -0.83832057429 
// 4.02661555369 1.07262016184 -1.75051518393 
// 2 0 1 
// 2 2 3

void test6()
{
    double p[3]={0};
    double p1[3]={2.19479724765, 0.08228617162, -0.93576115370};
    double p2[3]={2.29866822064, 2.07003002614, -0.74083438516 };
    double q1[3]={2.24677723010, 1.07615801043, -0.83832057429   };
    double q2[3]={4.02661555369, 1.07262016184, -1.75051518393 };
    int re=is_line_segment_intersecting_with_line_segment(p1,p2,q1,q2,p);

    printf("re:%d %f %f %f\n",re,p[0],p[1],p[2]);
}
// 0.51917934418 0.55711853504 0.72594100237 
// 1.21281309426 2.12527139485 0.48147824407 
// 1.90644684434 3.69342425466 0.23701548576 
// 2.60008059442 5.26157711446 -0.00744727254 
// 2 0 1 
// 2 2 3 

void test7()
{
    double p[3]={0};
    double p1[3]={0.51917934418, 0.55711853504, 0.72594100237};
    double p2[3]={1.21281309426, 2.12527139485, 0.48147824407 };
    double q1[3]={1.90644684434, 3.69342425466, 0.23701548576   };
    double q2[3]={2.60008059442, 5.26157711446, -0.00744727254 };
    int re=is_line_segment_intersecting_with_line_segment(q1,q2,p1,p2,p);

    printf("re:%d %f %f %f\n",re,p[0],p[1],p[2]);
}
// 0.64984464645 0.44046854973 0.19004359841 
// 2.04172158148 0.86624246836 1.12885737419 
// 1.34578311397 0.65335550904 0.65945048630 
// 2.73766004900 1.07912942767 1.59826426208 
// 2 0 1 
// 2 2 3 

void test8()
{
    double p[3]={0};
    double p1[3]={0.64984464645, 0.44046854973, 0.19004359841};
    double p2[3]={2.04172158148, 0.86624246836, 1.12885737419 };
    double q1[3]={1.34578311397, 0.65335550904, 0.65945048630   };
    double q2[3]={2.73766004900, 1.07912942767, 1.59826426208 };
    int re=is_line_segment_intersecting_with_line_segment(q1,q2,p1,p2,p);

    printf("re:%d %f %f %f\n",re,p[0],p[1],p[2]);
}
// -0.01909488253 0.11685097963 0.24613478780 
// 1.86455804296 0.42994422466 0.84094837308 
// 0.78501533158 1.26034764200 0.46015665680 
// 0.50958283432 3.23424772173 0.29338680953 
// 2 0 1 
// 2 2 3 

void test9()
{
    double p[3]={0};
    double p1[3]={-0.01909488253, 0.11685097963, 0.24613478780};
    double p2[3]={1.86455804296, 0.42994422466, 0.84094837308 };
    double q1[3]={0.78501533158, 1.26034764200, 0.46015665680   };
    double q2[3]={0.50958283432, 3.23424772173, 0.29338680953 };
    int re=is_line_segment_intersecting_with_line_segment(p1,p2,q1,q2,p);

    printf("re:%d %f %f %f\n",re,p[0],p[1],p[2]);
}


// -1.05788535625 1.49512481689 0.38148450851 
// 1.67091237754 0.73787471652 1.92285776138 
// 2.23556643724 -0.25805290043 1.55799287558 
// 1.89062125236 -1.00156381726 0.67933690548 
// -0.83817648143 -0.24431371689 -0.86203634739 
// -1.40283054113 0.75161390007 -0.49717146158 
// 2.12571199983 0.61166636646 2.17975330353 
// 2.34542087466 -1.12777216733 0.93623244762 
// 2 0 1 
// 2 1 2 
// 2 2 3 
// 2 3 4 
// 2 4 5 
// 2 5 0 
// 2 6 7 

void testa1()
{
    double ps[8][3]={{-1.05788535625, 1.49512481689, 0.38148450851},
        {1.67091237754, 0.73787471652, 1.92285776138},
        {2.23556643724, -0.25805290043, 1.55799287558},
        {1.89062125236, -1.00156381726, 0.67933690548 },
        {-0.83817648143, -0.24431371689, -0.86203634739},
        {-1.40283054113, 0.75161390007, -0.49717146158},
        {2.12571199983, 0.61166636646, 2.17975330353},
        {2.34542087466, -1.12777216733, 0.93623244762}
    };



    double *polygon[6]={ps[0],ps[1],ps[2],ps[3],ps[4],ps[5]};

    double *l= get_line_equation_from_two_points(ps[7],ps[6] );
    //
    double *ts=line_intersection_with_polygon(l,polygon,6);
    if(ts!=NULL)
    {
        printf("ts 1:%lf ts 2:%lf\n",ts[0],ts[1]);
        printf("point1:%lf %lf %lf point2:%lf %lf %lf\n",ts[0]*l[0]+l[3],ts[0]*l[1]+l[4],ts[0]*l[2]+l[5],
            ts[1]*l[0]+l[3],ts[1]*l[1]+l[4],ts[1]*l[2]+l[5]);
    }

    //double**polygon1= get_intersection_polygon_and_line(polygon,6,&len1 ,l);

    double *n= compute_plane_normal_of_jordan_curve(polygon,6 );
    normalize(n,3);
    printf("%lf %lf %lf\n",n[0],n[1],n[2]);


    double dir[3]={0,0,1};
    double *trans=get_one_dir_trans2dir_rota_matrix(n,dir);
    double ps1[8][3]={0};
    for(int i=0;i<8;i++)
    {   
        for(int j=0;j<3;j++)
        {
            ps1[i][j]=trans[j*3+0]*ps[i][0]+trans[j*3+1]*ps[i][1]+trans[j*3+2]*ps[i][2];
        }
        ps1[i][2]=0;
    }

    double l1[4]={ps1[6][0]-ps1[7][0],ps1[6][1]-ps1[7][1],ps1[6][0],ps1[6][1] };

    normalize(l1,2);
    l1[0]=l1[0];l1[1]=l1[1];
    double *polygon1[6]={ps1[0],ps1[1],ps1[2],ps1[3],ps1[4],ps1[5]};
    for(int i=0;i<6;i++)
    {
        printf("%lf %lf %lf\n",polygon1[i][0],polygon1[i][1],polygon1[i][2]);
    }
    int len=0;
    int tuihua=0;
    double**poly= get_half_section_polygon_and_line( polygon1,6,&len ,l1,&tuihua);


    printf("len:%d tuihua:%d\n",len,tuihua);
    for(int i=0;i<len;i++)
    {
        printf("%lf %lf %lf\n",poly[i][0],poly[i][1],poly[i][2]);
    }
    // for(int i=0;i<3;i++)
    // {
    //     printf("%lf\n",trans[i*3+0]*n[0]+trans[i*3+1]*n[1]+trans[i*3+2]*n[2]);
    // }

    SAFE_FREE(l);
    SAFE_FREE(n);
}
// -1.91739264131 2.30812329054 2.00044704601 
// 3.87199458480 0.75239610672 1.75018458441 
// 4.42744636536 -0.79318955541 0.23274494708 
// 3.05310240388 -1.82019948959 -1.20127386972 
// -2.73628482223 -0.26447230577 -0.95101140812 
// -3.29173660278 1.28111335635 0.56642822921 
// 3.11181975901 1.65483286977 2.52975960821 
// 1.88348148763 -2.20406052470 -1.89742807299 

void testa2()
{
    double ps[8][3]={{-1.91739264131, 2.30812329054, 2.00044704601 },
        {3.87199458480, 0.75239610672, 1.75018458441},
        {4.42744636536, -0.79318955541, 0.23274494708 },
        {3.05310240388, -1.82019948959, -1.20127386972 },
        {-2.73628482223, -0.26447230577, -0.95101140812},
        {-3.29173660278, 1.28111335635, 0.56642822921},
        {3.11181975901, 1.65483286977, 2.52975960821},
        {1.88348148763, -2.20406052470, -1.89742807299}
    };

    double *polygon[6]={ps[0],ps[1],ps[2],ps[3],ps[4],ps[5]};

    double *l= get_line_equation_from_two_points(ps[6],ps[7] );
    //
    double *ts=line_intersection_with_polygon(l,polygon,6);
    if(ts!=NULL)
    {
        printf("ts 1:%lf ts 2:%lf\n",ts[0],ts[1]);
        printf("point1:%lf %lf %lf point2:%lf %lf %lf\n",ts[0]*l[0]+l[3],ts[0]*l[1]+l[4],ts[0]*l[2]+l[5],
            ts[1]*l[0]+l[3],ts[1]*l[1]+l[4],ts[1]*l[2]+l[5]);
    }

    //double**polygon1= get_intersection_polygon_and_line(polygon,6,&len1 ,l);

    double *n= compute_plane_normal_of_jordan_curve(polygon,6 );
    normalize(n,3);
    printf("%lf %lf %lf\n",n[0],n[1],n[2]);


    double dir[3]={0,0,1};
    double *trans=get_one_dir_trans2dir_rota_matrix(n,dir);
    double ps1[8][3]={0};
    for(int i=0;i<8;i++)
    {   
        for(int j=0;j<3;j++)
        {
            ps1[i][j]=trans[j*3+0]*ps[i][0]+trans[j*3+1]*ps[i][1]+trans[j*3+2]*ps[i][2];
        }
        ps1[i][2]=0;
    }

    double l1[4]={ps1[6][0]-ps1[7][0],ps1[6][1]-ps1[7][1],ps1[6][0],ps1[6][1] };

    normalize(l1,2);
    l1[0]=-l1[0];l1[1]=-l1[1];
    double *polygon1[6]={ps1[0],ps1[1],ps1[2],ps1[3],ps1[4],ps1[5]};
    for(int i=0;i<6;i++)
    {
        printf("%lf %lf %lf\n",polygon1[i][0],polygon1[i][1],polygon1[i][2]);
    }
    int len=0;
    int tuihua=0;
    double**poly= get_half_section_polygon_and_line( polygon1,6,&len ,l1,&tuihua);


    printf("len:%d tuihua:%d\n",len,tuihua);
    for(int i=0;i<len;i++)
    {
        printf("%lf %lf %lf\n",poly[i][0],poly[i][1],poly[i][2]);
    }
    // for(int i=0;i<3;i++)
    // {
    //     printf("%lf\n",trans[i*3+0]*n[0]+trans[i*3+1]*n[1]+trans[i*3+2]*n[2]);
    // }

    SAFE_FREE(l);
    SAFE_FREE(n);
}
// -1.07267165184 1.69615120441 2.34065347910 
// 3.79676973820 1.80060308427 -1.16320663691 
// 3.85318726301 0.32374307513 -2.84118652344 
// 2.28645765781 -1.18793422729 -3.35121303797 
// -2.58298373222 -1.29238610715 0.15264707804 
// -2.63940125704 0.18447390199 1.83062696457 
// 5.41991686821 1.83542037755 -2.33116000891 
// 3.90960478783 -1.15311693400 -4.51916640997 

void testa3()
{
    double ps[8][3]={{-1.07267165184, 1.69615120441, 2.34065347910 },
        {3.79676973820, 1.80060308427, -1.16320663691},
        {3.85318726301, 0.32374307513, -2.84118652344},
        {2.28645765781, -1.18793422729, -3.35121303797 },
        {-2.58298373222, -1.29238610715, 0.15264707804 },
        {-2.63940125704, 0.18447390199, 1.83062696457},
        {5.41991686821, 1.83542037755, -2.33116000891},
        {3.90960478783, -1.15311693400, -4.51916640997}
    };

    double *polygon[6]={ps[0],ps[1],ps[2],ps[3],ps[4],ps[5]};

    double *l= get_line_equation_from_two_points(ps[6],ps[7] );
    //
    double *ts=line_intersection_with_polygon(l,polygon,6);
    if(ts!=NULL)
    {
        printf("ts 1:%lf ts 2:%lf\n",ts[0],ts[1]);
        printf("point1:%lf %lf %lf point2:%lf %lf %lf\n",ts[0]*l[0]+l[3],ts[0]*l[1]+l[4],ts[0]*l[2]+l[5],
            ts[1]*l[0]+l[3],ts[1]*l[1]+l[4],ts[1]*l[2]+l[5]);
    }

    //double**polygon1= get_intersection_polygon_and_line(polygon,6,&len1 ,l);

    double *n= compute_plane_normal_of_jordan_curve(polygon,6 );
    normalize(n,3);
    printf("%lf %lf %lf\n",n[0],n[1],n[2]);


    double dir[3]={0,0,1};
    double *trans=get_one_dir_trans2dir_rota_matrix(n,dir);
    double ps1[8][3]={0};
    for(int i=0;i<8;i++)
    {   
        for(int j=0;j<3;j++)
        {
            ps1[i][j]=trans[j*3+0]*ps[i][0]+trans[j*3+1]*ps[i][1]+trans[j*3+2]*ps[i][2];
        }
        ps1[i][2]=0;
    }

    double l1[4]={ps1[6][0]-ps1[7][0],ps1[6][1]-ps1[7][1],ps1[6][0],ps1[6][1] };

    normalize(l1,2);
    l1[0]=l1[0];l1[1]=l1[1];
    double *polygon1[6]={ps1[0],ps1[1],ps1[2],ps1[3],ps1[4],ps1[5]};
    for(int i=0;i<6;i++)
    {
        printf("%lf %lf %lf\n",polygon1[i][0],polygon1[i][1],polygon1[i][2]);
    }
    int len=0;
    int tuihua=0;
    double**poly= get_half_section_polygon_and_line( polygon1,6,&len ,l1,&tuihua);


    printf("len:%d tuihua:%d\n",len,tuihua);
    for(int i=0;i<len;i++)
    {
        printf("%lf %lf %lf\n",poly[i][0],poly[i][1],poly[i][2]);
    }
    // for(int i=0;i<3;i++)
    // {
    //     printf("%lf\n",trans[i*3+0]*n[0]+trans[i*3+1]*n[1]+trans[i*3+2]*n[2]);
    // }

    SAFE_FREE(l);
    SAFE_FREE(n);
}
// 1.07879948616 1.56619147933 0.32185079157 
// 1.94648828357 1.82920572069 -0.13980509341 
// 2.56585013866 1.58445794717 -0.90900938213 
// 1.94503278285 0.31505291001 -1.67788039148 
// 0.45798213035 0.29678644217 -0.44702021778 
// 1.94794378430 3.34335853136 1.39827020466 
// 1.94357728213 -1.19909990067 -3.21595568955 

void testa4()
{
    double ps[7][3]={{1.07879948616, 1.56619147933, 0.32185079157 },
        {1.94648828357, 1.82920572069, -0.13980509341},
        {2.56585013866, 1.58445794717, -0.90900938213},
        {1.94503278285, 0.31505291001, -1.67788039148 },
        {0.45798213035, 0.29678644217, -0.44702021778 },
        {1.94794378430, 3.34335853136, 1.39827020466},
        {1.94357728213, -1.19909990067, -3.21595568955}
    };



    double *polygon[5]={ps[0],ps[1],ps[2],ps[3],ps[4]};

    double *l= get_line_equation_from_two_points(ps[6],ps[5] );
    //
    double *ts=line_intersection_with_polygon(l,polygon,5);
    if(ts!=NULL)
    {
        printf("ts 1:%lf ts 2:%lf\n",ts[0],ts[1]);
        printf("point1:%lf %lf %lf point2:%lf %lf %lf\n",ts[0]*l[0]+l[3],ts[0]*l[1]+l[4],ts[0]*l[2]+l[5],
            ts[1]*l[0]+l[3],ts[1]*l[1]+l[4],ts[1]*l[2]+l[5]);
    }

    //double**polygon1= get_intersection_polygon_and_line(polygon,6,&len1 ,l);

    double *n= compute_plane_normal_of_jordan_curve(polygon,5 );
    normalize(n,3);
    printf("%lf %lf %lf\n",n[0],n[1],n[2]);


    double dir[3]={0,0,1};
    double *trans=get_one_dir_trans2dir_rota_matrix(n,dir);
    double ps1[7][3]={0};
    for(int i=0;i<7;i++)
    {   
        for(int j=0;j<3;j++)
        {
            ps1[i][j]=trans[j*3+0]*ps[i][0]+trans[j*3+1]*ps[i][1]+trans[j*3+2]*ps[i][2];
        }
        ps1[i][2]=0;
    }

    double l1[4]={ps1[5][0]-ps1[6][0],ps1[5][1]-ps1[6][1],ps1[5][0],ps1[5][1] };

    normalize(l1,2);
    l1[0]=-l1[0];l1[1]=-l1[1];
    double *polygon1[5]={ps1[0],ps1[1],ps1[2],ps1[3],ps1[4]};
    for(int i=0;i<5;i++)
    {
        printf("%lf %lf %lf\n",polygon1[i][0],polygon1[i][1],polygon1[i][2]);
    }
    int len=0;
    int tuihua=0;
    double**poly= get_half_section_polygon_and_line( polygon1,5,&len ,l1,&tuihua);


    printf("len:%d tuihua:%d\n",len,tuihua);
    for(int i=0;i<len;i++)
    {
        printf("%lf %lf %lf\n",poly[i][0],poly[i][1],poly[i][2]);
    }
    // for(int i=0;i<3;i++)
    // {
    //     printf("%lf\n",trans[i*3+0]*n[0]+trans[i*3+1]*n[1]+trans[i*3+2]*n[2]);
    // }

    SAFE_FREE(l);
    SAFE_FREE(n);
}
// 1.30471283197 1.55400141701 0.32625738531 
// 2.30337431282 2.04878568649 -0.22239830345 
// 3.14507067204 1.85496876016 -1.11522593349 
// 2.75265786797 0.13346577063 -1.97565578669 
// 0.91230002791 -0.16750157252 -0.53417246789 
// 2.69578711689 3.77028867602 0.63803154975 
// 1.51854870468 -1.39422029257 -1.94325800985 

void testa5()
{
    double ps[7][3]={{1.30471283197, 1.55400141701, 0.32625738531 },
        {2.30337431282, 2.04878568649, -0.22239830345},
        {3.14507067204, 1.85496876016, -1.11522593349},
        {2.75265786797, 0.13346577063, -1.97565578669 },
        {0.91230002791, -0.16750157252, -0.53417246789 },
        {2.69578711689, 3.77028867602, 0.63803154975},
        {1.51854870468, -1.39422029257, -1.94325800985 }
    };



    double *polygon[5]={ps[0],ps[1],ps[2],ps[3],ps[4]};

    double *l= get_line_equation_from_two_points(ps[5],ps[6] );
    //
    double *ts=line_intersection_with_polygon(l,polygon,5);
    if(ts!=NULL)
    {
        printf("ts 1:%lf ts 2:%lf\n",ts[0],ts[1]);
        printf("point1:%lf %lf %lf point2:%lf %lf %lf\n",ts[0]*l[0]+l[3],ts[0]*l[1]+l[4],ts[0]*l[2]+l[5],
            ts[1]*l[0]+l[3],ts[1]*l[1]+l[4],ts[1]*l[2]+l[5]);
    }

    //double**polygon1= get_intersection_polygon_and_line(polygon,6,&len1 ,l);

    double *n= compute_plane_normal_of_jordan_curve(polygon,5 );
    normalize(n,3);
    printf("%lf %lf %lf\n",n[0],n[1],n[2]);


    double dir[3]={0,0,1};
    double *trans=get_one_dir_trans2dir_rota_matrix(n,dir);
    double ps1[7][3]={0};
    for(int i=0;i<7;i++)
    {   
        for(int j=0;j<3;j++)
        {
            ps1[i][j]=trans[j*3+0]*ps[i][0]+trans[j*3+1]*ps[i][1]+trans[j*3+2]*ps[i][2];
        }
        ps1[i][2]=0;
    }

    double l1[4]={ps1[5][0]-ps1[6][0],ps1[5][1]-ps1[6][1],ps1[5][0],ps1[5][1] };

    normalize(l1,2);
    l1[0]=l1[0];l1[1]=l1[1];
    double *polygon1[5]={ps1[0],ps1[1],ps1[2],ps1[3],ps1[4]};
    for(int i=0;i<5;i++)
    {
        printf("%lf %lf %lf\n",polygon1[i][0],polygon1[i][1],polygon1[i][2]);
    }
    int len=0;
    int tuihua=0;
    double**poly= get_half_section_polygon_and_line( polygon1,5,&len ,l1,&tuihua);


    printf("len:%d tuihua:%d\n",len,tuihua);
    for(int i=0;i<len;i++)
    {
        printf("%lf %lf %lf\n",poly[i][0],poly[i][1],poly[i][2]);
    }
    // for(int i=0;i<3;i++)
    // {
    //     printf("%lf\n",trans[i*3+0]*n[0]+trans[i*3+1]*n[1]+trans[i*3+2]*n[2]);
    // }

    SAFE_FREE(l);
    SAFE_FREE(n);
}
// -0.79197019339 -0.80591979623 -0.68519228697 
// 0.62652941048 4.84708473086 1.77060472965 
// 2.88024932146 0.21492633224 -1.89863425493 
// -1.00077527016 1.76537093520 0.84606671333 
// 2.67144424468 2.78621706367 -0.36737525463 

void testa6()
{
    double ps[5][3]={{-0.79197019339, -0.80591979623, -0.68519228697 },
        {0.62652941048, 4.84708473086, 1.77060472965},
        {2.88024932146, 0.21492633224, -1.89863425493},
        {-1.00077527016, 1.76537093520, 0.84606671333 },
        {2.67144424468, 2.78621706367, -0.36737525463 }
    };



    double *polygon[3]={ps[0],ps[1],ps[2]};

    double *l= get_line_equation_from_two_points(ps[3],ps[4] );
    //
    double *ts=line_intersection_with_polygon(l,polygon,3);
    if(ts!=NULL)
    {
        printf("ts 1:%lf ts 2:%lf\n",ts[0],ts[1]);
        printf("point1:%lf %lf %lf point2:%lf %lf %lf\n",ts[0]*l[0]+l[3],ts[0]*l[1]+l[4],ts[0]*l[2]+l[5],
            ts[1]*l[0]+l[3],ts[1]*l[1]+l[4],ts[1]*l[2]+l[5]);
    }

    //double**polygon1= get_intersection_polygon_and_line(polygon,6,&len1 ,l);

    double *n= compute_plane_normal_of_jordan_curve(polygon,3 );
    normalize(n,3);
    printf("%lf %lf %lf\n",n[0],n[1],n[2]);


    double dir[3]={0,0,1};
    double *trans=get_one_dir_trans2dir_rota_matrix(n,dir);
    double ps1[5][3]={0};
    for(int i=0;i<5;i++)
    {   
        for(int j=0;j<3;j++)
        {
            ps1[i][j]=trans[j*3+0]*ps[i][0]+trans[j*3+1]*ps[i][1]+trans[j*3+2]*ps[i][2];
        }
        ps1[i][2]=0;
    }

    double l1[4]={ps1[3][0]-ps1[4][0],ps1[3][1]-ps1[4][1],ps1[3][0],ps1[3][1] };

    normalize(l1,2);
    l1[0]=-l1[0];l1[1]=-l1[1];
    double *polygon1[3]={ps1[0],ps1[1],ps1[2]};
    for(int i=0;i<3;i++)
    {
        printf("%lf %lf %lf\n",polygon1[i][0],polygon1[i][1],polygon1[i][2]);
    }
    int len=0;
    int tuihua=0;
    double**poly= get_half_section_polygon_and_line( polygon1,3,&len ,l1,&tuihua);


    printf("len:%d tuihua:%d\n",len,tuihua);
    for(int i=0;i<len;i++)
    {
        printf("%lf %lf %lf\n",poly[i][0],poly[i][1],poly[i][2]);
    }
    // for(int i=0;i<3;i++)
    // {
    //     printf("%lf\n",trans[i*3+0]*n[0]+trans[i*3+1]*n[1]+trans[i*3+2]*n[2]);
    // }

    SAFE_FREE(l);
    SAFE_FREE(n);
}
// 0.58869689703 0.31956145540 0.20342232287 
// 1.23701852560 1.22126564756 1.22178198397 
// 1.73904454708 1.34623626992 1.34889988601 
// 1.25280332565 0.66995812580 0.58513014019 
// 1.75482934713 0.79492874816 0.71224804223 
// 2.11055976152 0.14316580072 -0.05187581480 
// 1.60853374004 0.01819517836 -0.17899371684 
// 1.39909893274 1.44669169560 1.47637189925 
// 2.46629017591 -0.50859714672 -0.81599967182 
void testa7()
{
    double ps[9][3]={{0.58869689703, 0.31956145540, 0.20342232287 },
        {1.23701852560, 1.22126564756, 1.22178198397},
        {1.73904454708, 1.34623626992, 1.34889988601},
        {1.25280332565, 0.66995812580, 0.58513014019  },
        {1.75482934713, 0.79492874816, 0.71224804223 },
        {2.11055976152, 0.14316580072, -0.05187581480},
        {1.60853374004, 0.01819517836, -0.17899371684},
        {1.39909893274, 1.44669169560, 1.47637189925},
        {2.46629017591, -0.50859714672, -0.81599967182}
    };



    double *polygon[7]={ps[0],ps[1],ps[2],ps[3],ps[4],ps[5],ps[6]};

    double *l= get_line_equation_from_two_points(ps[7],ps[8] );
    //
    double *ts=line_intersection_with_polygon(l,polygon,7);
    if(ts!=NULL)
    {
        printf("ts 1:%lf ts 2:%lf\n",ts[0],ts[1]);
        printf("point1:%lf %lf %lf point2:%lf %lf %lf\n",ts[0]*l[0]+l[3],ts[0]*l[1]+l[4],ts[0]*l[2]+l[5],
            ts[1]*l[0]+l[3],ts[1]*l[1]+l[4],ts[1]*l[2]+l[5]);
    }

    //double**polygon1= get_intersection_polygon_and_line(polygon,6,&len1 ,l);

    double *n= compute_plane_normal_of_jordan_curve(polygon,7 );
    normalize(n,3);
    printf("%lf %lf %lf\n",n[0],n[1],n[2]);


    double dir[3]={0,0,1};
    double *trans=get_one_dir_trans2dir_rota_matrix(n,dir);
    double ps1[9][3]={0};
    for(int i=0;i<9;i++)
    {   
        for(int j=0;j<3;j++)
        {
            ps1[i][j]=trans[j*3+0]*ps[i][0]+trans[j*3+1]*ps[i][1]+trans[j*3+2]*ps[i][2];
        }
        ps1[i][2]=0;
    }

    double l1[4]={ps1[7][0]-ps1[8][0],ps1[7][1]-ps1[8][1],ps1[7][0],ps1[7][1] };

    normalize(l1,2);
    l1[0]=l1[0];l1[1]=l1[1];
    double *polygon1[7]={ps1[0],ps1[1],ps1[2],ps1[3],ps1[4],ps1[5],ps1[6]};
    for(int i=0;i<7;i++)
    {
        printf("%lf %lf %lf\n",polygon1[i][0],polygon1[i][1],polygon1[i][2]);
    }
    int len=0;
    int tuihua=0;
    double**poly= get_half_section_polygon_and_line( polygon1,7,&len ,l1,&tuihua);


    printf("len:%d tuihua:%d\n",len,tuihua);
    for(int i=0;i<len;i++)
    {
        printf("%lf %lf %lf\n",poly[i][0],poly[i][1],poly[i][2]);
    }
    // for(int i=0;i<3;i++)
    // {
    //     printf("%lf\n",trans[i*3+0]*n[0]+trans[i*3+1]*n[1]+trans[i*3+2]*n[2]);
    // }

    SAFE_FREE(l);
    SAFE_FREE(n);
}

// -0.9999998807907104 0.0000000437113883 2.3444576263427734
// -1.0000000000000000 0.0000000437113883 -0.9999999403953552
// 1.0000002384185791 -0.0000000437113883 4.3551139831542969
// 0.9999999403953552 -0.0000000437113883 -1.0000000000000000
// 3.0298531055450439 -0.0000001324390837 2.3444573879241943
// 3.0298531055450439 -0.0000001324390837 -1.0000001192092896
// -1.3378894329071045 -1.1760282516479492 -1.8963940143585205
// 0.3298583030700684 -1.2550185918807983 -0.7953133583068848
// -1.8248789310455322 0.5615931749343872 -1.0341219902038574
// -0.1571312546730042 0.4826028347015381 0.0669586658477783

void testb1()
{
    double ps[10][3]={{-0.9999998807907104, 0.0000000437113883, 2.3444576263427734 },
        {-1.0000000000000000, 0.0000000437113883, -0.9999999403953552},
        {1.0000002384185791, -0.0000000437113883, 4.3551139831542969},
        {0.9999999403953552, -0.0000000437113883, -1.0000000000000000  },
        {3.0298531055450439, -0.0000001324390837, 2.3444573879241943 },
        {3.0298531055450439, -0.0000001324390837, -1.0000001192092896},
        {-1.3378894329071045, -1.1760282516479492, -1.8963940143585205},
        {0.3298583030700684, -1.2550185918807983, -0.7953133583068848},
        {-1.8248789310455322, 0.5615931749343872, -1.0341219902038574},
        {-0.1571312546730042, 0.4826028347015381, 0.0669586658477783}
    };

    double *polygon1[6]={ps[0],ps[2],ps[4],ps[5],ps[3],ps[1]};

    double *polygon2[4]={ps[6],ps[7],ps[9],ps[8]};
    int jinhua=0;
    double ** mark_ps=get_intersection_points_from_two_polygons(polygon1,6,polygon2 ,4,&jinhua);

    printf("jinhua:%d\n",jinhua);
    if(mark_ps!=NULL)
    {
        printf("mark ps1:%lf %lf %lf mark ps2:%lf %lf %lf\n",mark_ps[0][0],mark_ps[0][1],mark_ps[0][2],
            mark_ps[1][0],mark_ps[1][1],mark_ps[1][2]);
    }

}
// 0.000372 -0.062815 2.637109 
// 0.000372 -0.062815 -0.707348 
// 2.000372 -0.062815 4.647766 
// 2.000372 -0.062815 -0.707348 
// 4.030225 -0.062815 2.637109 
// 4.030225 -0.062815 -0.707349 
// -1.3378894329071045 -1.1760282516479492 -1.8963940143585205
// 0.3298583030700684 -1.2550185918807983 -0.7953133583068848
// -1.8248789310455322 0.5615931749343872 -1.0341219902038574
// -0.1571312546730042 0.4826028347015381 0.0669586658477783

void testb2()
{
    double ps[10][3]={{0.000372, -0.062815, 2.637109 },
        {0.000372, -0.062815, -0.707348},
        {2.000372, -0.062815, 4.647766},
        {2.000372, -0.062815, -0.707348 },
        {4.030225, -0.062815, 2.637109 },
        {4.030225, -0.062815, -0.707349},
        {-1.3378894329071045, -1.1760282516479492, -1.8963940143585205},
        {0.3298583030700684, -1.2550185918807983, -0.7953133583068848},
        {-1.8248789310455322, 0.5615931749343872, -1.0341219902038574},
        {-0.1571312546730042, 0.4826028347015381, 0.0669586658477783}
    };

    double *polygon1[6]={ps[0],ps[2],ps[4],ps[5],ps[3],ps[1]};

    double *polygon2[4]={ps[6],ps[7],ps[9],ps[8]};
    int jinhua=0;
    double ** mark_ps=get_intersection_points_from_two_polygons(polygon1,6,polygon2 ,4,&jinhua);

    printf("jinhua:%d\n",jinhua);
    if(mark_ps!=NULL)
    {
        printf("mark ps1:%lf %lf %lf mark ps2:%lf %lf %lf\n",mark_ps[0][0],mark_ps[0][1],mark_ps[0][2],
            mark_ps[1][0],mark_ps[1][1],mark_ps[1][2]);
    }
}
// -3.870218 -0.021471 1.658096 
// -3.870219 -0.021471 -1.686361 
// -1.870218 -0.021471 3.668752 
// -1.870219 -0.021471 -1.686361 
// 0.159635 -0.021471 1.658096 
// 0.159635 -0.021471 -1.686362 
// -1.3378894329071045 -1.1760282516479492 -1.8963940143585205
// 0.3298583030700684 -1.2550185918807983 -0.7953133583068848
// -1.8248789310455322 0.5615931749343872 -1.0341219902038574
// -0.1571312546730042 0.4826028347015381 0.0669586658477783

void testb3()
{
    double ps[10][3]={{-3.870218, -0.021471, 1.658096 },
        {-3.870219, -0.021471, -1.686361},
        {-1.870218, -0.021471, 3.668752 },
        {-1.870219, -0.021471, -1.686361  },
        { 0.159635, -0.021471, 1.658096 },
        {0.159635, -0.021471, -1.686362},
        {-1.3378894329071045, -1.1760282516479492, -1.8963940143585205},
        {0.3298583030700684, -1.2550185918807983, -0.7953133583068848},
        {-1.8248789310455322, 0.5615931749343872, -1.0341219902038574},
        {-0.1571312546730042, 0.4826028347015381, 0.0669586658477783}
    };

    
    double *polygon1[6]={ps[0],ps[2],ps[4],ps[5],ps[3],ps[1]};

    double *polygon2[4]={ps[6],ps[7],ps[9],ps[8]};
    int jinhua=0;
    double ** mark_ps=get_intersection_points_from_two_polygons(polygon1,6,polygon2 ,4,&jinhua);

    printf("jinhua:%d\n",jinhua);
    if(mark_ps!=NULL)
    {
        printf("mark ps1:%lf %lf %lf mark ps2:%lf %lf %lf\n",mark_ps[0][0],mark_ps[0][1],mark_ps[0][2],
            mark_ps[1][0],mark_ps[1][1],mark_ps[1][2]);
    }
}
// 0.485979 0.072988 2.672720 
// 0.485979 0.072988 -0.671737 
// 2.485979 0.072987 4.683377 
// 2.485979 0.072987 -0.671737 
// 4.515832 0.072987 2.672720 
// 4.515832 0.072987 -0.671737 
// -1.3378894329071045 -1.1760282516479492 -1.8963940143585205
// 0.3298583030700684 -1.2550185918807983 -0.7953133583068848
// -1.8248789310455322 0.5615931749343872 -1.0341219902038574
// -0.1571312546730042 0.4826028347015381 0.0669586658477783

void testb4()
{
    double ps[10][3]={{0.485979, 0.072988, 2.672720 },
        {0.485979, 0.072988, -0.671737},
        {2.485979, 0.072987, 4.683377 },
        {2.485979, 0.072987, -0.671737  },
        {4.515832, 0.072987, 2.672720},
        {4.515832, 0.072987, -0.671737},
        {-1.3378894329071045, -1.1760282516479492, -1.8963940143585205},
        {0.3298583030700684, -1.2550185918807983, -0.7953133583068848},
        {-1.8248789310455322, 0.5615931749343872, -1.0341219902038574},
        {-0.1571312546730042, 0.4826028347015381, 0.0669586658477783}
    };

    double *polygon1[6]={ps[0],ps[2],ps[4],ps[5],ps[3],ps[1]};

    double *polygon2[4]={ps[6],ps[7],ps[9],ps[8]};
    int jinhua=0;
    double ** mark_ps=get_intersection_points_from_two_polygons(polygon1,6,polygon2 ,4,&jinhua);

    printf("jinhua:%d\n",jinhua);
    if(mark_ps!=NULL)
    {
        printf("mark ps1:%lf %lf %lf mark ps2:%lf %lf %lf\n",mark_ps[0][0],mark_ps[0][1],mark_ps[0][2],
            mark_ps[1][0],mark_ps[1][1],mark_ps[1][2]);
    }
}
// 1.028418 -0.496194 0.834359 
// 1.128137 -1.849219 2.303842 
// 3.184973 -2.841608 3.972561 
// 5.042371 -1.127947 2.702313 
// 4.942653 0.225078 1.232829 
// 2.556310 -3.773443 1.796207 
// 2.656029 -5.126468 3.265690 
// 6.570263 -4.405196 3.664160 
// 6.470545 -3.052171 2.194677 

void testb5()
{
    double ps[9][3]={{1.028418, -0.496194, 0.834359 },
        {1.128137, -1.849219, 2.303842},
        {3.184973, -2.841608, 3.972561 },
        {5.042371, -1.127947, 2.702313  },
        {4.942653, 0.225078, 1.232829},
        {2.556310, -3.773443, 1.796207},
        {2.656029, -5.126468, 3.265690 },
        {6.570263, -4.405196, 3.664160},
        {6.470545, -3.052171, 2.194677}
    };

    double *polygon1[5]={ps[0],ps[1],ps[2],ps[3],ps[4]};

    double *polygon2[4]={ps[5],ps[6],ps[7],ps[8]};
    int jinhua=0;
    double ** mark_ps=get_intersection_points_from_two_polygons(polygon1,5,polygon2 ,4,&jinhua);

    printf("jinhua:%d\n",jinhua);
    if(mark_ps!=NULL)
    {
        printf("mark ps1:%lf %lf %lf mark ps2:%lf %lf %lf\n",mark_ps[0][0],mark_ps[0][1],mark_ps[0][2],
            mark_ps[1][0],mark_ps[1][1],mark_ps[1][2]);
    }
}
// 1.099155 0.864303 0.211737 
// 1.579607 2.229025 1.592570 
// 3.777916 3.957632 2.016043 
// 5.015322 2.956795 -0.322150 
// 4.534870 1.592073 -1.702983 
// 2.678761 3.093329 1.804306 
// 3.159213 4.458051 3.185139 
// 6.594929 5.185821 1.270420 
// 6.114477 3.821099 -0.110413 

void testb6()
{
    double ps[9][3]={{1.099155, 0.864303, 0.211737},
        {1.579607, 2.229025, 1.592570},
        {3.777916, 3.957632, 2.016043},
        {5.015322, 2.956795, -0.322150  },
        {4.534870, 1.592073, -1.702983},
        {2.678761, 3.093329, 1.804306 },
        {3.159213, 4.458051, 3.185139},
        {6.594929, 5.185821, 1.270420},
        {6.114477, 3.821099, -0.110413}
    };

    double *polygon1[5]={ps[0],ps[1],ps[2],ps[3],ps[4]};

    double *polygon2[4]={ps[5],ps[6],ps[7],ps[8]};
    int jinhua=0;
    double ** mark_ps=get_intersection_points_from_two_polygons(polygon1,5,polygon2 ,4,&jinhua);

    printf("jinhua:%d\n",jinhua);
    if(mark_ps!=NULL)
    {
        printf("mark ps1:%lf %lf %lf mark ps2:%lf %lf %lf\n",mark_ps[0][0],mark_ps[0][1],mark_ps[0][2],
            mark_ps[1][0],mark_ps[1][1],mark_ps[1][2]);
    }
}

// -1.709298 0.215134 2.159651 
// -1.709299 0.215134 -1.184806 
// 0.290702 0.215134 4.170307 
// 0.290701 0.215134 -1.184806 
// 2.320555 0.215134 2.159651 
// 2.320555 0.215134 -1.184807 
// -1.3378894329071045 -1.1760282516479492 -1.8963940143585205
// 0.3298583030700684 -1.2550185918807983 -0.7953133583068848
// -1.8248789310455322 0.5615931749343872 -1.0341219902038574
// -0.1571312546730042 0.4826028347015381 0.0669586658477783


void testb7()
{
    double ps[10][3]={{-1.709298, 0.215134 ,2.159651 },
        {-1.709299, 0.215134, -1.184806},
        {0.290702, 0.215134, 4.170307 },
        {0.290701, 0.215134, -1.184806 },
        {2.320555, 0.215134, 2.159651 },
        {2.320555, 0.215134, -1.184807},
        {-1.3378894329071045, -1.1760282516479492, -1.8963940143585205},
        {0.3298583030700684, -1.2550185918807983, -0.7953133583068848},
        {-1.8248789310455322, 0.5615931749343872, -1.0341219902038574},
        {-0.1571312546730042, 0.4826028347015381, 0.0669586658477783}
    };

    double *polygon1[6]={ps[0],ps[2],ps[4],ps[5],ps[3],ps[1]};

    double *polygon2[4]={ps[6],ps[7],ps[9],ps[8]};
    int jinhua=0;
    double ** mark_ps=get_intersection_points_from_two_polygons(polygon1,6,polygon2 ,4,&jinhua);

    printf("jinhua:%d\n",jinhua);
    if(mark_ps!=NULL)
    {
        printf("mark ps1:%lf %lf %lf mark ps2:%lf %lf %lf\n",mark_ps[0][0],mark_ps[0][1],mark_ps[0][2],
            mark_ps[1][0],mark_ps[1][1],mark_ps[1][2]);
    }
}
// -2.289742 2.110037 1.213541 
// -0.963531 -1.602686 1.453039 
// 2.210618 -1.884519 0.051008 
// 2.209987 1.172939 -0.650594 
// 0.047498 0.793784 0.435704 
// 0.938415 2.305736 2.405596 
// -0.427019 0.446084 2.683841 
// -0.510441 0.104171 0.851833 

void testb8()
{
    double ps[8][3]={{-2.289742, 2.110037, 1.213541  },
        {-0.963531, -1.602686 ,1.453039},
        {2.210618, -1.884519, 0.051008 },
        {2.209987, 1.172939, -0.650594 },
        {0.047498, 0.793784, 0.435704  },
        {0.938415, 2.305736, 2.405596 },
        {-0.427019, 0.446084 ,2.683841},
        {-0.510441, 0.104171 ,0.851833 }
    };

    double *polygon1[4]={ps[0],ps[1],ps[2],ps[3]};

    double *polygon2[4]={ps[4],ps[5],ps[6],ps[7]};
    int jinhua=0;
    double ** mark_ps=get_intersection_points_from_two_polygons(polygon1,4,polygon2 ,4,&jinhua);

    printf("jinhua:%d\n",jinhua);
    if(mark_ps!=NULL)
    {
        printf("mark ps1:%lf %lf %lf mark ps2:%lf %lf %lf\n",mark_ps[0][0],mark_ps[0][1],mark_ps[0][2],
            mark_ps[1][0],mark_ps[1][1],mark_ps[1][2]);
    }
}
// -2.029745 1.925960 0.447047 
// -0.759910 -1.575783 -1.010699 
// 4.104263 -1.590933 0.518903 
// 3.743769 2.082867 2.355457 
// -1.932637 -0.728223 1.419549 
// -0.857018 1.078400 -1.983201 
// -5.672636 -0.233541 -3.026552 
// -4.391760 -0.792739 -0.567562 

void testb9()
{
    double ps[8][3]={{-2.029745, 1.925960, 0.447047  },
        {-0.759910, -1.575783, -1.010699},
        {4.104263, -1.590933, 0.518903  },
        {3.743769, 2.082867, 2.355457  },
        {-1.932637, -0.728223, 1.419549   },
        {-0.857018, 1.078400, -1.983201 },
        {-5.672636, -0.233541, -3.026552},
        {-4.391760, -0.792739, -0.567562 }
    };

    double *polygon1[4]={ps[0],ps[1],ps[2],ps[3]};

    double *polygon2[4]={ps[4],ps[5],ps[6],ps[7]};
    int jinhua=0;
    double ** mark_ps=get_intersection_points_from_two_polygons(polygon1,4,polygon2 ,4,&jinhua);

    printf("jinhua:%d\n",jinhua);
    if(mark_ps!=NULL)
    {
        printf("mark ps1:%.9lf %.9lf %.9lf mark ps2:%.9lf %.9lf %.9lf\n",mark_ps[0][0],mark_ps[0][1],mark_ps[0][2],
            mark_ps[1][0],mark_ps[1][1],mark_ps[1][2]);
    }
}
// 1 5 0
// 2 1 0
// 4 1 0
// 5 3 0
// 3 2 0
// 2 4 0
// 3 4 0
// 2 5 0
// 2 6 0

void testc1()
{
    double ps[9][3]={{1, 5, 0  },
        {2, 1, 0},
        {4, 1, 0  },
        {5, 3, 0 },
        {3, 2, 0  },
        {2, 4, 0 },
        {3, 4, 0},
        {2, 5, 0 },
        {2, 6, 0}
    };

    double *polygon1[9]={ps[0],ps[1],ps[2],ps[3],ps[4],ps[5],ps[6],ps[7],ps[8]};
    int **s=(int**)malloc(sizeof(int*)*(9-2) );
    for(int i=0;i<(9-2);i++)
    {
        s[i]=(int*)malloc(sizeof(int)*3);
    }
    //double *polygon2[4]={ps[4],ps[5],ps[6],ps[7]};
    subdivision_of_polygon(polygon1,9,s);

    for(int i=0;i<(9-2);i++)
    {
        printf("3 %d %d %d\n",s[i][0],s[i][1],s[i][2]);
    }
}
// 1 1 0
// 8 1 0
// 4 4.8 0
// 4 2 0
// 2 3 0
// 4 5 0
// 5 4 0
// 6 6 0
// 2 6 0
void testc2()
{

    double ps[9][3] = {
        {1, 1, 0},
        {8, 1, 0},
        {4, 4.8, 0},
        {4, 2, 0},
        {2, 3, 0},
        {4, 5, 0},
        {5, 4, 0},
        {6, 6, 0},
        {2, 6, 0}
    };
    double* polygon1[9] = { ps[0],ps[1],ps[2],ps[3],ps[4],ps[5],ps[6],ps[7],ps[8] };
    int** s = (int**)malloc(sizeof(int*) * (9 - 2));
    //printf("%d\n", pts_num);
    for (int i = 0; i < (9 - 2); i++)
    {
        s[i] = (int*)malloc(sizeof(int) * 3);
        memset(s[i], 0, sizeof(int) * 3);
    }
    //double *polygon2[4]={ps[4],ps[5],ps[6],ps[7]};
    subdivision_of_polygon(polygon1, 9, s);
    for (int i = 0; i < (9 - 2); i++)
    {
        printf("3 %d %d %d\n", s[i][0], s[i][1], s[i][2]);
    }
}


void testc3()
{
    double ps[10][3] = {
        {1,5,0},
        {2,1,0},
        {3,1,0},
        {4,1,0},
        {5,3,0},
        {3,2,0},
        {2,4,0},
        {3,4,0},
        {2,5,0},
        {2,6,0}
    };
    double* polygon1[10] = { ps[0],ps[1],ps[2],ps[3],ps[4],ps[5],ps[6],ps[7],ps[8],ps[9] };
    int** s = (int**)malloc(sizeof(int*) * (10 - 2));
    //printf("%d\n", pts_num);
    for (int i = 0; i < (10 - 2); i++)
    {
        s[i] = (int*)malloc(sizeof(int) * 3);
        memset(s[i], 0, sizeof(int) * 3);
    }
    //double *polygon2[4]={ps[4],ps[5],ps[6],ps[7]};
    optimization_subdivision_of_polygon(polygon1, 10, s);
    for (int i = 0; i < (10 - 2); i++)
    {
        printf("3 %d %d %d\n", s[i][0], s[i][1], s[i][2]);
    }
}
void testc4()
{
    double ps[10][3] = {
        {1,1,0},
        {7.99995,1,0},
        {8,1,0},
        {4,4.8,0},
        {4,2,0},
        {2,3,0},
        {4,5,0},
        {5,4,0},
        {6,6,0},
        {2,6,0}
    };
    double* polygon1[10] = { ps[0],ps[1],ps[2],ps[3],ps[4],ps[5],ps[6],ps[7],ps[8],ps[9] };
    int** s = (int**)malloc(sizeof(int*) * (10 - 2));
    //printf("%d\n", pts_num);
    for (int i = 0; i < (10 - 2); i++)
    {
        s[i] = (int*)malloc(sizeof(int) * 3);
        memset(s[i], 0, sizeof(int) * 3);
    }
    //double *polygon2[4]={ps[4],ps[5],ps[6],ps[7]};
    subdivision_of_polygon(polygon1, 10, s);
    //optimization_subdivision_of_polygon(polygon1, 10, s);
    for (int i = 0; i < (10 - 2); i++)
    {
        printf("3 %d %d %d\n", s[i][0], s[i][1], s[i][2]);
    }
}
void testc5()
{
    double ps[7][3] = {
        {-2,1,0},
        {2,1,0},
        {2,5,0},
        {0.0005,2,0},
        {0,7,0},
        {-0.0005,2,0},
        {-2,5,0}
    };
    double* polygon1[10] = { ps[0],ps[1],ps[2],ps[3],ps[4],ps[5],ps[6]};
    int** s = (int**)malloc(sizeof(int*) * (7 - 2));
    //printf("%d\n", pts_num);
    for (int i = 0; i < (7 - 2); i++)
    {
        s[i] = (int*)malloc(sizeof(int) * 3);
        memset(s[i], 0, sizeof(int) * 3);
    }
    //double *polygon2[4]={ps[4],ps[5],ps[6],ps[7]};
    subdivision_of_polygon(polygon1, 7, s);
    //optimization_subdivision_of_polygon(polygon1, 10, s);
    for (int i = 0; i < (7 - 2); i++)
    {
        printf("3 %d %d %d\n", s[i][0], s[i][1], s[i][2]);
    }
}
// 2 1 0
// 3 2 0
// 2 3 0
// 1.5 3 0
// -1 2 0
// 1.5 1 0

// -2 1 0
// -3 2 0
// -2 3 0
// -1.5 3 0
// 1 2 0
// -1.5 1 0
// 6 0 1 2 3 4 5
// 6 6 7 8 9 10 11
int testd1()
{

    double ps[12][3]={{2, 1, 0},
        {3, 2, 0},
        {2, 3, 0},
        {1.5, 3, 0 },
        {-1, 2, 0},
        {1.5, 1, 0 },
        {-2, 1, 0},
        {-3, 2, 0},
        {-2, 3, 0},
        {-1.5, 3, 0},
        {1, 2, 0},
        {-1.5, 1, 0}
    };

    double *polygon1[6]={ps[0],ps[1],ps[2],ps[3],ps[4],ps[5]};

    double *polygon2[6]={ps[6],ps[7],ps[8],ps[9],ps[10],ps[11]};
    int tuihua=0;int len=0;

    double** poly = get_intersection_polygon_and_polygon(polygon1,6,polygon2,6,&len,&tuihua);
    
    //printf("len:%d ",len);

    for(int i=0;i<len;i++)
    {
        free(poly[i]);
    }
    free(poly);
    return len;
}
int testd2()
{

    double ps[5][3]={{13.356293107843713,  30.814923150507781, 3.6055384535205564},
        {13.300116029516174,  30.96903918806327, 3.6382248735293046},
        {12.979317362742901,  30.908076190183955, 3.6080685549869087},
        {13.604227394995137,  30.956852066724224, 3.6662838282740822 },
        {13.34315378010491,  30.700237553421104, 3.5665224833173741}
    };

    double *polygon1[3]={ps[0],ps[1],ps[2]};

    double *polygon2[3]={ps[3],ps[1],ps[4]};
    int tuihua=0;int len=0;

    double** poly = get_intersection_polygon_and_polygon(polygon1,3,polygon2,3,&len,&tuihua);
    
    printf("len:%d %d",len,tuihua);

    for(int i=0;i<len;i++)
    {
        free(poly[i]);
    }
    free(poly);
    return len;
}
// -50.0811 1.3926
// -50.01863 1.404387
// -50.05226 1.189347
// -49.734010 0.214385
// -50.0855 1.290452 
// -50.36778 2.416162
//
int testd3()
{

    double ps[6][3]={{-50.0811, 1.3926, 0.0},
        {-50.01863, 1.404387, 0.0},
        {-50.05226, 1.189347, 0.0},
        {-49.734010, 0.214385,0.0 },
        {-50.0855, 1.290452,0.0},
        {-50.36778, 2.416162,0.0}
    };

    double *polygon1[3]={ps[1],ps[0],ps[2]};

    double *polygon2[3]={ps[4],ps[3],ps[5]};
    int tuihua=0;int len=0;

    double** poly = get_intersection_polygon_and_polygon(polygon1,3,polygon2,3,&len,&tuihua);
    
    printf("len:%d %d",len,tuihua);

    for(int i=0;i<len;i++)
    {
        free(poly[i]);
    }
    free(poly);
    return len;
}
// poly1
// 13.356293107843713  30.814923150507781 3.6055384535205564
// 13.300116029516174  30.96903918806327 3.6382248735293046
// 12.979317362742901  30.908076190183955 3.6080685549869087
// poly2
// 13.604227394995137  30.956852066724224 3.6662838282740822
// 13.300116029516174  30.96903918806327 3.6382248735293046
// 13.34315378010491  30.700237553421104 3.5665224833173741
// cid:1648
// 1648 0.036421900 0.183857600 0.874124500
// 1648 0.038469600 0.188578200 0.865042100
// 1648 0.033303200 0.177572500 0.859003600
// cid:3844
// 3844 0.035168500 0.181284500 0.865725600
// 3844 0.024777700 0.199528000 0.845685500
// 3844 0.023910900 0.184167600 0.869836800

void teste1()
{
    double ps[6][3]={{0.036421900, 0.183857600, 0.874124500 },
        {0.038469600, 0.188578200, 0.865042100},
        {0.033303200, 0.177572500, 0.859003600  },
        {0.035168500, 0.181284500, 0.865725600  },
        {0.024777700, 0.199528000, 0.845685500 },
        {0.023910900, 0.184167600, 0.869836800 }
    };

    double *polygon1[3]={ps[0],ps[1],ps[2]};

    double *polygon2[3]={ps[3],ps[4],ps[5]};
    int jinhua=0;
    double ** mark_ps=get_intersection_points_from_two_polygons(polygon1,3,polygon2 ,3,&jinhua);

    printf("jinhua:%d\n",jinhua);
    if(mark_ps!=NULL)
    {
        printf("mark ps1:%.9lf %.9lf %.9lf mark ps2:%.9lf %.9lf %.9lf\n",mark_ps[0][0],mark_ps[0][1],mark_ps[0][2],
            mark_ps[1][0],mark_ps[1][1],mark_ps[1][2]);
    }

}

// 0.125124 0.650001 0.175867
// 0.125140 0.649984 0.175856
// 0.125127 0.650003 0.175868
// 0.125175 0.649872 0.175786
// 0.125871 0.647978 0.174585
// 0.125773 0.648243 0.174753
// 0.124908 0.652017 0.177138
// 0.124916 0.651945 0.177107
// 0.124902 0.651948 0.177109
// 0.125818 0.647964 0.174575
// 0.125197 0.651874 0.177066
// 0.122389 0.652579 0.177474

void teste2()
{
    double ps[12*3]={0.125124, 0.650001, 0.175867,
0.125140, 0.649984, 0.175856,
0.125127, 0.650003, 0.175868,
0.125175, 0.649872, 0.175786,
0.125871, 0.647978, 0.174585,
0.125773, 0.648243, 0.174753,
0.124908, 0.652017, 0.177138,
0.124916, 0.651945, 0.177107,
0.124902, 0.651948, 0.177109,
0.125818, 0.647964, 0.174575,
0.125197, 0.651874, 0.177066,
0.122389, 0.652579, 0.177474
    };

    double *polygon1[4]={&ps[7*3],&ps[10*3],&ps[5*3],&ps[0*3]};

    int**s1=(int**)malloc(sizeof(int*)*2);
    for(int i=0;i<2;i++)
    {
        s1[i]=(int*)malloc(sizeof(int)*3);
    }
    double *polygon2[6]={&ps[11*3],&ps[6*3],&ps[8*3],&ps[7*3],&ps[0*3],&ps[5*3]};

    int**s2=(int**)malloc(sizeof(int*)*4);
    for(int i=0;i<4;i++)
    {
        s2[i]=(int*)malloc(sizeof(int)*3);
    }
    optimization_subdivision_of_polygon(polygon1,4,s1);
    printf("end on\n");
    optimization_subdivision_of_polygon(polygon2,6,s2);

    for(int i=0;i<2;i++)
    {
        printf("%d %d %d\n",s1[i][0],s1[i][1],s1[i][2]);
    }
    for(int i=0;i<4;i++)
    {
        printf("%d %d %d\n",s2[i][0],s2[i][1],s2[i][2]);
    }
}

int main()
{
    clock_t t = clock();

    // test1();
    // test2();
    // test3();
    // test4();
    // test5();
    // test6();
    // test7();
    // test8();
    // test9();

    // testa1();
    // testa2();
    //testa3();
    //testa4();
    //testa5();
    //testa6();
    // testa7();
    // testb1();
    //testb2();
    //testb3();
    //testb4();
    //testb5();
    //testb6();
    //testb7();
    //testb8();
    //testb9();
    //testc1();
    //testc2();
    //testc3();
    //testc4();
    // testc5();
    //testd2();
    //teste2();
    testd3();
    int num=0;
    for(int i=0;i<900000;i++)
    {
        num+=testd1();

    }
    printf("运行时间%.4f秒:%d\n", (double)(clock() - t) / CLOCKS_PER_SEC,num); 
    printf("%d\n",19%5);

    printf("end \n");
    return 0;
}